New algorithms for modular inversion and representation by binary quadratic forms arising from structure in the Euclidean algorithm

摘要

We observe structure in the sequences of quotients and remainders of theEuclidean algorithm with two families of inputs. Analyzing the remainders, weobtain new algorithms for computing modular inverses and representating primenumbers by the binary quadratic form $x^2 + 3xy + y^2$. The Euclidean algorithmis commenced with inputs from one of the families, and the first remainder lessthan a predetermined size produces the modular inverse or representation.